import datastructure.linklist.ListNode;

import java.util.List;
import java.util.Stack;

/**
 * @author ZCR
 * @create 2025/9/8 20:43
 */
public class Solution445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2);
            l2 = l2.next;
        }
        ListNode head = new ListNode(0);
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int a = stack1.isEmpty() ? 0 : stack1.pop().val;
            int b = stack2.isEmpty() ? 0 : stack2.pop().val;
            int sum = a + b + carry;
            carry = sum / 10;
            ListNode temp  = new ListNode(sum % 10);
            temp.next = head.next;
            head.next = temp;
        }
        if (carry > 0) {
            ListNode temp  = new ListNode(carry);
            temp.next = head.next;
            head.next = temp;
        }
        return head.next;
    }

    public static void main(String[] args) {
        Solution445 solution445 = new Solution445();
        ListNode l1 = ListNode.arrayToList(new int[]{7, 2, 4, 3});
        ListNode l2 = ListNode.arrayToList(new int[]{5, 6, 4});
        ListNode.printListWithCycleCheck(solution445.addTwoNumbers(l1, l2));
    }
}
